class Solution(object):
    def getMaximumGold(self, grid):
        m = len(grid)
        n = len(grid[0])
        max_len = 0
        def search(x, y):
            now = grid[x][y]
            grid[x][y] = 0
            next_v = 0
            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= ux < m and 0 <= uy < n:
                    if grid[ux][uy]:
                        next_v = max(next_v, search(ux, uy))
            grid[x][y] = now
            return now + next_v

        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    max_len = max(max_len, search(i, j))
        return max_len


